#include <algorithm>
using namespace std;
class Solution {
    vector<vector<int> > ans;
    vector<int> num, tmp;
    void run(vector<int> &candidates, int target, int h) {
        if (candidates.size()==h) {
            if (target!=0) return;
            tmp.clear();
            for (int i=0;i<num.size();i++)
                for (int j=0;j<num[i];j++)
                    tmp.push_back(candidates[i]);
            ans.push_back(tmp);
            return;
        }
        if (0<target && target<candidates[h]) return;
        for (num[h]=0;num[h]<=target/candidates[h];num[h]++)
            run(candidates, target-candidates[h]*num[h], h+1);
    }
public:
    vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
        ans.clear();
        sort(candidates.begin(), candidates.end());
        num.resize(candidates.size(), 0);
        run(candidates, target, 0);
        return ans;
    }
};
